<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Free CSS Templates
http://www.freecsstemplates.org
Released for free under a Creative Commons Attribution 2.5 License
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>CSC560 Design and Analysis of Real-Time Systems</title>
<meta name="keywords" content="" />
<meta name="description" content="" />
<link href="../default.css" rel="stylesheet" type="text/css" />
		<link href="../js/default.css" rel="stylesheet" type="text/css" />
<script type="text/javascript" src="../js/highlight.pack.js"></script>
<script type="text/javascript" src="../js/highlight.js"></script>
<script src="../js/avrasm.js"></script>
<script src="../js/cpp.js"></script>
<script type="text/javascript">
hljs.initHighlightingOnLoad();
</script>
</head>
<body>
<div id="wrapper">
	<div id="header">
		<h1>CSC560</h1>
		<h2>Design and Analysis of Real-Time Systems</h2>
		<ul>
			<li class="first">
				<a href="../index.html" accesskey="1" title="">Home</a>
			</li>
			<li>
				<a href="../project1/index.html" accesskey="2" title="">Project 1</a>
			</li>
			<li>
				<a href="index.html" accesskey="3" title=""><b>Project 2</b></a>
			</li>
			<li>
				<a href="../project3/index.html" accesskey="4" title="">Project 3</a>
			</li>
			<li>
				<a href="../project4/index.html" accesskey="4" title="">Project 4</a>
			</li>
			<li>
				<a href="../project5/index.html" accesskey="4" title="">Project 5</a>
			</li>
		</ul>
	</div>
</div>
<div id="content">
	<div id="colOne">
		<h2>System and Round Robin Scheduling</h2>
		<h3>Introduction</h3>
		<p>
			“System level tasks are FCFS; they run to completion, i.e., until they terminate, block or yield. Thus, they are non-preemptible, not even by 
			other system tasks.” Hence, a system task should generally not be enclosed in a ‘for’ loop and then attemp to yield by invoking Task_Next(). 
			Otherwise, it will simply be suspended and then resume right away repeatly if there no other system-level tasks.  
			<br>
			<br>
			Round robin (RR) tasks take turn to execute and each task executes for one tick at a time. A running RR 
			task can be preempted by a system or periodic task. It is therefore unnecessary, unless intended, to yield in a 
			round robin task because it’s executed for 1 tick each time and RTOS will force it to yield and move it back to the end of the RR task queue. 
		</p>		
		<p>
			For this part we were required to use mixture of system and round robin tasks. We decided to apply scheduling policies 
			to the four tasks as follows:
			<br><br>
				<li>Joystick task:<br> 
					Round robin task because it took minimum time and not urgent.</li><br>
				<li>Radio Transmission task: 
					<br>System task, because it took few ticks and the SCI command had to be sent 
					so that the next SCI command could be sent for the joystick to be more responsive.</li><br>
				<li>Radio Receiving task: 
					<br>System task, because it took few ticks and the SPI Rx buffer 
					had to be cleared in time.</li><br>
				<li>UART task:
				<br>Round robin, because it was not urgent and more of a background task.</li>
			<br>
			<br>
			
			The following diagram shows a typical execution of the joystick, radio send/receive and uart tasks.
			<br><br>
			<a href="../images/system_rr_diagram.jpg"><img src="../images/system_rr_diagram.jpg" alt="Sequence diagram for System and ROUND ROBIN" align="center" width="100%"/></a>
			<br><br>
			The first ROUND ROBIN task is the joystick. It executes for 1 tick, and then if the user does not press any joystick command,
			the second ROUND ROBIN task, i.e. uart, executes. Both the joystick and uart tasks alternates between each other 
			until the user presses a command on the joystick. The system task, i.e. <i>radio tx</i>, is put to sleep and wakes up every 45 ticks. It is crucial
			that the sleep time is not to short nor too long as it greatly affects the responsiveness of commands execution. Indeed, if this task's sleep time is 
			1 tick for example, it keeps waking up, and does not give much chance for other RR tasks to run. On the other hand, if the task sleeps for too long, 
			there will be some time wasted between the time a joystick movement is pressed and the time it is actually executed, which will greatly affect the responsiveness
			of the commands. In addition, since it is a system task, it executes to completion. Now, on the receiving side, an interrupt occurs when we receive the status packet back from the roomba.
			At this time, a system task is created, i.e <i>radio rx</i>. This task executes to completion. It collects information such as distance, start time, and 
			end time which will be needed for the uart task. Note that it is possible that after the <i>radio tx</i> task finishes executing, and before the <i>radio receive</i> 
			task executes, uart and joystick tasks execute in a round robin fashion. Therefore, the sequence diagram would slightly differ.		
		</p>
		<p>
			The view of the system is as follow: The main function creates the joystick, radio tx and uart tasks. Whenever the Joystick task is 
			executing and asserts that a joystick movement is detected, it prepares a SCI command. When the radio tx tasks wakes up, it checks whether
			there is a packet to be transmitted. Whenever a status packet arrives, the corresponding interrupt service routine (ISR) creates a Radio Receiving task. 
			Lastly, uart task prints out the speeds whenever the receive task has set the print flag to 1. 
			The two system tasks were created only when necessary so to conserve runtime RTOS resources.
		</p>

		
		<h3>Observations</h3>
			<p>
			At first, we observed that calculated speeds were not correct and had high diversity. This was odd as the speeds 
			calculated were correct when periodic tasks were used. In an attempt to resolve it, we tried various mixtures of 
			System and Round Robin scheduling policies without success. After hours of debugging we concluded that it was caused 
			by our implementation of Radio Receiving task, where the start time and end time for the packet roundtrip were recorded 
			for speed calculation. 
			<br><br>
			For example, at times when the Radio Receiving task was executing, the status packet had not 
			arrived yet for the first SCI command packet sent. Hence, the start time and end time were not recorded by the Radio 
			Receiving task. Later, after the second SCI packet had been sent, the Radio Receiving task processed the status packet 
			corresponding to the first SCI command packet and the start time and end time were recorded for speed calculation. 
			As a result, speed calculated was incorrect because the end time was associated with the 2nd packet but the start 
			time was associated with the first packet.			
		</p>
		<p>
			The essence of this problem was the 'timing'. The time to process a receiving packet should be exact, neither too early nor too late. 
			Therefore, to resolve it, we initially enclosed the Radio Receiving task in a “for” loop to wait for the arrival of the status 
			packet. The task was then terminated once the status packet had been processed. This gave the correct calculated 
			speeds. Nevertheless, later on we adopted another approach to resolve it. Instead of having the Radio Receiving 
			task created by the Radio Transmission task, the former was created by the ISR that corresponded to arrival of 
			status packet. This approach was more appropriate and precise because it was certain then that the status packet 
			had arrived for the Radio Receiving task to process. 
					
		</p>
		
		<p>Another example of timing is related to the time the radio tx task sleeps. For example, the following function shows
		the fragment of code for the radio tx task. 
		
		<pre>
<code class="cpp">void task_radio_send(void) {
	for (;;) {
		if (joystick_flag) {
			joystick_flag = 0;
			Radio_Transmit(&command_packet, 
					RADIO_WAIT_FOR_TX);
		}
		Task_Sleep(45); //must sleep for right time
				//not too long, not too short
	}
}
</code>
</pre>

	We started by modifying the Task_Sleep() call as follow:
	
			<pre>
<code class="cpp">void task_radio_send(void) {
	for (;;) {
		...
		Task_Sleep(1);	//too short sleep
	}
}
</code>
</pre>
	This resulted in a too short sleep time for the system task. As a consequence, the radio tx task 
	was executing for most of the time, leaving no time for the RR tasks to execute. 
		</p>
		
	<p>
		We therefore increased the sleep time to 100 as follow:
					<pre>
<code class="cpp">void task_radio_send(void) {
	for (;;) {
		...
		Task_Sleep(100);	//too short sleep
	}
}
</code>
</pre>
	This ended up being too long. Joystick movements were not responsive. The command took too long to execute.
	</p>	
	
	We therefore used a time between 1 and 100. With trials and errors, we ended up with a sleep time of 45, which 
	made the joystick movement very responsive.
	
	</div>
	
	<div id="colTwo">
		<h3>Project Sections</h3>
		<ul>
			<li class="first"><a href="part1.html">Time Measurements</a></li>
			<li>	<a href="part2.html">Scheduling Tasks with RTOS</a></li>
			<li>-	<a href="part2sub1.html">Periodic</a></li>
			<li>-	<a href="part2sub2.html">System and Round Robin</a></li>
			<li>-	<a href="part2sub3.html">Event Coordinated</a></li>
						<li>	<a href="doxygen/html/index.html">Doxygen</a></li>
						<li><a href="http://code.google.com/p/wireless-roomba">Google Code</a></li>

		</ul>
	</div>
</div>
<div id="footer">
	<p>@ 2009. All Rights Reserved. Design by <a href="http://www.freecsstemplates.org/">Free CSS Templates</a>.</p>
</div>
</body>
</html>
